package algorithms.dynamicProgram;

import java.util.List;
import java.util.Queue;

public class LeetCode_120 {

    public static void main(String[] args) {

    }


    /**
     * 解法1：自顶向下，二维数组，
     * 状态方程：dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j]
     * <p>
     * 有个问题：
     * <p>
     * 解法2：
     * 求出来的结果是一个数组，需要对数组里的值取最小值，属于多余的计算。
     * 反过来，自底向上，求出来的结果就在 dp[0][0] 当中.
     * 状态方程：dp[i][j] = min(dp[i+1][j+1],dp[i+1][j]) + triangle[i][j]
     * <p>
     * 解法3：
     * 滚动的一维数组对空间复杂度进行优化。
     *
     * @param triangle
     * @return
     */
    public int minimumTotal1(List<List<Integer>> triangle) {
        if (triangle.size() == 1) {
            return triangle.get(0).get(0);
        }
        int length = triangle.size();
        int[][] dp = new int[length][length];
        for (int i = 0; i < length; i++) {
            dp[length - 1][i] = triangle.get(length - 1).get(i);
        }
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i + 1][j + 1], dp[i + 1][j]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];


    }

    /**
     * 解法3：
     * 滚动的一维数组对空间复杂度进行优化。
     *
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle.size() == 1) {
            return triangle.get(0).get(0);
        }
        int length = triangle.size();
        int[] dp = new int[length];
        for (int i = 0; i < length; i++) {
            dp[i] = triangle.get(length - 1).get(i);
        }
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i; j >= 0; j--) {
                dp[j] = Math.min(dp[j + 1], dp[j]) + triangle.get(i).get(j);
            }
        }
        return dp[0];


    }
}
